/**
 * 
 */
package edu.arizona.bio5.onto.decomposition.locality;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import org.semanticweb.owlapi.apibinding.OWLManager;
import org.semanticweb.owlapi.model.OWLAxiom;
import org.semanticweb.owlapi.model.OWLEntity;
import org.semanticweb.owlapi.model.OWLOntology;
import org.semanticweb.owlapi.model.OWLOntologyCreationException;
import org.semanticweb.owlapi.model.OWLOntologyManager;
import org.semanticweb.owlapi.modularity.OntologySegmenter;

import uk.ac.manchester.cs.owlapi.modularity.ModuleType;
import uk.ac.manchester.cs.owlapi.modularity.SyntacticLocalityModuleExtractor;
import uk.ac.manchester.cs.util.SetUtils;
import edu.arizona.bio5.onto.decomposition.Atom;
import edu.arizona.bio5.onto.decomposition.AtomicDecomposition;
import edu.arizona.bio5.onto.decomposition.AxiomSet;
import edu.arizona.bio5.onto.decomposition.MSSLabel;

/*
 * Improvements needed:
 * - Intelligent (goal directed) signature refinement procedure
 * - Fast term-based indexes for sets
 */


/**
 * Uses module extraction to minimize seed signatures.
 * 
 * 
 * @author Pavel Klinov
 *
 */
public class SeedSigFinderWithExtraction extends PISeedSignatureFinder {
	
	static int SIG_CNT = 0;

	private static final long REFINEMENT_TIME_LIMIT = 1000;


	public SeedSigFinderWithExtraction(ModuleType mType) {
	
		super(mType);
	}

	
	
	@Override
	public Collection<Set<OWLEntity>> findMinSeedSignatures(Atom atom, AtomicDecomposition ad) {
		// TODO Auto-generated method stub
		Collection<Set<OWLEntity>> seedSigs = super.findMinSeedSignatures(atom, ad);
		boolean labelComplete = getMSSLabel(atom).isComplete();
		
		//System.out.print("Refining starts...");
		
		boolean complete = refine(seedSigs, atom, ad, false);
		
		//System.out.println("... ends!");
		
		atom.setLabel(new MSSLabel(seedSigs, labelComplete & complete));
		
		return seedSigs;
	}



	/*
	 * Runs the refinement procedure for every seed signature candidate.
	 * 
	 * It returns a boolean flag indicating whether it managed to compute all min seed signatures or not
	 */
	protected boolean refine(Collection<Set<OWLEntity>> seedSigs, Atom atom, AtomicDecomposition ad, boolean testTopLevelSigs) {
		
		AxiomSet pIdeal = ad.getPrincipalIdeal(atom);
		Collection<Set<OWLEntity>> newSeedSigs = new ArrayList<Set<OWLEntity>>();
		Collection<Set<OWLEntity>> knownNonSeedSigs = new ArrayList<Set<OWLEntity>>();
		boolean complete = true;
		long startTime = System.currentTimeMillis();
		
		try {
			
			OWLOntologyManager manager = OWLManager.createOWLOntologyManager();
			OWLOntology piOntology = manager.createOntology(pIdeal.getAxioms());
			OntologySegmenter extractor = new SyntacticLocalityModuleExtractor(manager, piOntology, getModuleType());
			
			for (Set<OWLEntity> seedSig : seedSigs) {

				RefinementResult refResult = refineSeedSignature(seedSig, atom, extractor, newSeedSigs, knownNonSeedSigs, startTime, testTopLevelSigs);
				
				complete &= refResult.mIsComplete;
			}
		} catch (OWLOntologyCreationException e) {
			// Should never happen!
			e.printStackTrace();
			throw new RuntimeException(e);
		}
		
		seedSigs.clear();
		seedSigs.addAll(newSeedSigs);	
		
		return complete;
	}
	
	/*
	 * Checks if the signature is indeed a seed signature for the principal ideal
	 * If yes, tries to figure out if some subsets are also seed signatures
	 * 
	 * WARNING: This method has exponential worst-case complexity (in the size of the signature)!
	 * TODO Need a more intelligent seed signature refinement
	 */
	protected RefinementResult refineSeedSignature(	Set<OWLEntity> seedSig,
													Atom atom,
													OntologySegmenter extractor,
													Collection<Set<OWLEntity>> newSeedSigs,
													Collection<Set<OWLEntity>> knownNonSeedSigs,
													long startTime,
													boolean testTopLevelSigs) {

		if (!testTopLevelSigs || isSeedSignature(seedSig, atom, extractor, newSeedSigs, knownNonSeedSigs)) {

			boolean result = false;
			boolean complete = true;
			
			if ((System.currentTimeMillis() - startTime) < REFINEMENT_TIME_LIMIT ) {
				//Still have some time, continue the breadth-first search
				for (OWLEntity term : seedSig) {

					Set<OWLEntity> copySig = new HashSet<OWLEntity>(seedSig);

					copySig.remove(term);
					
					RefinementResult refResult = refineSeedSignature(copySig, atom, extractor,	newSeedSigs, knownNonSeedSigs, startTime, true); 
					
					result |= refResult.mIsSeedSignature;
					complete &= refResult.mIsComplete;
				}

			} else {
				//Can't continue the breadth-first search any more, just run down to find some sub-signature
				for (Iterator<OWLEntity> termIter = seedSig.iterator(); termIter.hasNext();) {

					OWLEntity term = termIter.next();
					termIter.remove();
					
					if (!isSeedSignature(seedSig, atom, extractor, newSeedSigs, knownNonSeedSigs)) {
						
						result = false;
						seedSig.add(term);
						break;
					}
				}
				
				//System.err.println("Too costly to find all min sub-signatures. Found this: " + seedSig);
				complete = false;
			}
			
			if (!result) {
				//The signature is a minimal seed signature
				SetUtils.addAndMinimizeWrtInclusion(seedSig, newSeedSigs);
			}
			
			return new RefinementResult(true, complete);
		}
		
		return new RefinementResult(false, true);
	}

	
	private boolean isSeedSignature(Set<OWLEntity> seedSig,
									Atom atom,
									OntologySegmenter extractor,
									Collection<Set<OWLEntity>> knownSeedSigs,
									Collection<Set<OWLEntity>> knownNonSeedSigs) {
		//TODO Need a better data structure to speed up these operation (look at term-based indexing) 
		if (SetUtils.containsSubset(knownSeedSigs, seedSig)) {
			//We've seen a subset of this signature that was a seed signature, so the answer is true
			return true;
		}
		
		if (SetUtils.containsSuperset(knownNonSeedSigs, seedSig)) {
			//We've seen a superset of this signature that was NOT a seed signature, so the answer is false
			return false;
		}
		//No luck, have to check
		Set<OWLAxiom> pulledAxioms = extractor.extract(seedSig);		
		//See if all axioms from the atom are pulled in
		if (pulledAxioms.containsAll(atom.getAxioms()) ) {
			
			return true;
			
		} else {
			//Remember that the signature is not a seed signature
			//SetUtils.addAndMinimizeWrtInclusion(seedSig, knownNonSeedSigs);
			knownNonSeedSigs.add(seedSig);
			
			return false;
		}
	}
	
	class RefinementResult {
		
		boolean mIsSeedSignature = false;
		boolean mIsComplete = false;
		
		RefinementResult(boolean isSeedSig, boolean isComplete) {
			
			mIsSeedSignature = isSeedSig;
			mIsComplete = isComplete;
		}
	}
}
